package cn.edu.ncepu;

import java.util.ArrayList;
import java.util.List;

/**
 * 线性筛（欧拉筛）：筛选出小于等于n的所有素数
 */
public class LinearSieve {

    /**
     * 线性筛算法实现
     * @param n 上限值
     * @return 小于等于n的所有素数列表
     */
    public static List<Integer> sieve(int n) {
        // 存储每个数的最小质因数（Minimum Prime Factor），初始值为0
        int[] mpfs = new int[n + 1];
        // 存储筛选出的素数
        List<Integer> pn = new ArrayList<>();

        // 遍历2到n
        for (int i = 2; i <= n; i++) {
            int mpf = mpfs[i];
            // 若最小质因数为0，说明i是素数
            if (mpf == 0) {
                pn.add(i);
                mpf = i; // 素数的最小质因数是自身
            }

            // 遍历已找到的素数，筛去合数
            for (int p : pn) {
                // 若当前素数大于i的最小质因数，或乘积超过n，停止循环
                if (p > mpf) {
                    break;
                }
                int x = p * i;
                if (x > n) {
                    break;
                }
                // 设置合数x的最小质因数为p
                mpfs[x] = p;
            }
        }

        return pn;
    }

    public static void main(String[] args) {
        // 测试用例：筛选20以内的素数
        int n = 20;
        List<Integer> primes = sieve(n);
        System.out.println(primes);
    }
}